/*
 * Copyright (C), 2015-2018
 * FileName: Solution075
 * Author:   zhao
 * Date:     2018/12/17 18:27
 * Description: 75. 颜色分类
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

/**
 * 〈一句话功能简述〉<br>
 * 〈75. 颜色分类〉
 *
 * @author zhao
 * @date 2018/12/17 18:27
 * @since 1.0.1
 */
public class Solution075 {
    /**************************************
     * 题目

     给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

     此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

     注意:
     不能使用代码库中的排序函数来解决这道题。

     示例:

     输入: [2,0,2,1,1,0]
     输出: [0,0,1,1,2,2]
     进阶：

     一个直观的解决方案是使用计数排序的两趟扫描算法。
     首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
     你能想出一个仅使用常数空间的一趟扫描算法吗？
     **************************************/

    /*************************************
     想法：
     遍历数组，同时拥有三个游标

     left游标用来表示0的分界点(左边都是0)，right游标用来表示2的分界点(右边都是2)

     tmp游标表示正在游走的指针

     当遇到数字2的时候，就将tmp和right的值交换，这时候right值为2，所以就把right往前移一位

     当遇到数字0的时候，就将tmp和left的值交换，这时候left值为0，所以就把left往前移一位，同时tmp肯定不为2，所以往后移一位

     当遇到数字0的时候，就将tmp++;

     执行过程：
     arr =  [2, 0, 2, 1, 1, 0],left = 0,right = 5,tmp = 0
     第一轮：arr[tmp] == 2   >>  swap(arr[tmp],swap[right])  >> [0, 0, 2, 1, 1, 2],left = 0,right = 4,tmp = 0
     第二轮：arr[tmp] == 0   >>  swap(arr[tmp],swap[left])  >> [0, 0, 2, 1, 1, 2],left = 1,right = 4,tmp = 1
     第三轮：arr[tmp] == 0   >>  swap(arr[tmp],swap[left])  >> [0, 0, 2, 1, 1, 2],left = 2,right = 4,tmp = 2
     第四轮：arr[tmp] == 2   >>  swap(arr[tmp],swap[right])  >> [0, 0, 2, 1, 1, 2],left = 2,right = 3,tmp = 2

     我的做法
     超过  %的测试案例
     时间复杂度/空间复杂度：  /
     代码执行过程：

     代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git](https://gitee.com/lizhaoandroid/LeetCodeAll.git)
     查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan](https://blog.csdn.net/cmqwan)

     总结：

     ************************************/
    public void sortColors(int[] nums) {
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        int tmpIndex = 0;
        // 0、2的时候进行交换
        while (tmpIndex < rightIndex) {
            int num = nums[tmpIndex];
            if (num == 1) {
                tmpIndex++;
            }
            if (num == 0) {
                swapArrByIndex(nums, tmpIndex, leftIndex);
                leftIndex++;
                tmpIndex++;
            }
            if (num == 2) {
                swapArrByIndex(nums, tmpIndex, rightIndex);
                rightIndex--;
            }
        }

    }

    private static void swapArrByIndex(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    /**************************************
     * 比我好的答案 better
     * 二次遍历法
     * ***********************************/
    public void better(int[] nums) {
        int a = 0, b = 0, c = 0;
        for (int n : nums) {
            if (n == 0) {
                a++;
            } else if (n == 1) {
                b++;
            } else if (n == 2) {
                c++;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (a != 0) {
                nums[i] = 0;
                a--;
            } else if (b != 0) {
                nums[i] = 1;
                b--;
            } else if (c != 0) {
                nums[i] = 2;
                c--;
            }
        }
    }
}
